#include "seq_string.c"


// BF 匹配算法实现
// 没匹配到时，返回-1
int indexOf_BF(String str, String pattern)
{
    int i = 0, j = 0;
    while (i < str.length && j < pattern.length)
    {
        if (str.ch[i] == pattern.ch[j])
        {
            i++;
            j++;
        }
        else
        {
            i = i - j + 1;
            j = 0;
        }
    }
    if (j >= pattern.length)
    {
        return i - pattern.length;
    }
    else
    {
        return -1;
    }
}


void getNext(String pattern, int *next)
{
    int i = 0, j = -1;
    next[0] = -1;
    while (i < pattern.length - 1)
    {
        if (j == -1 || pattern.ch[i] == pattern.ch[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }
}

// 打印数组
print(String str)
{   
    int* next = (int *)malloc(str.length);
    getNext(str, next);
    for (int i = 0; i < str.length; i ++) 
    {
        printf("%d\t", i);
    }
    printf("\n");
    for (int i = 0; i < str.length; i++)
    {
        printf("%c\t", str.ch[i]);
    }
    printf("\n");
    for (int i = 0; i < str.length; i++)
    {
        printf("%d\t", next[i]);
    }
    printf("\n");
    printf("\n");
}

// 定义方法：indexOf_KMP
// 没匹配到时，返回-1
int indexOf_KMP(String str, String pattern)
{
    int i = 0, j = 0;
    int *next = (int *)malloc(pattern.length);
    getNext(pattern, next);
    // print(pattern);
    while (i < str.length && j < pattern.length)
    {
        if (j == -1 || str.ch[i] == pattern.ch[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
    if (j >= pattern.length)
    {
        return i - pattern.length;
    }
    else
    {
        return -1;
    }
}

// 测试 BF
void testBF()
{
    String s, t;
    int pos;
    initString(&s);
    initString(&t);
    s.ch = "aaaaaaab";
    s.length = 8;
    t.ch = "aaab";
    t.length = 4;
    pos = indexOf_BF(s, t);
    printf("pos = %d\n", pos);
}

// 测试 KMP
void testKMP()
{
    String s, t;
    int pos;
    initString(&s);
    initString(&t);
    // s.ch = "我也想过过过儿过过的生活";
    // s.length = 24;
    // t.ch = "过儿";
    // t.length = 4;
    s.ch = "aaaaaaab";
    s.length = 8;
    t.ch = "aaab";
    t.length = 4;
    // s.ch = "abcabcad";
    // s.length = 8;
    // t.ch = "abcad";
    // t.length = 5;
    pos = indexOf_KMP(s, t);
    printf("pos = %d\n", pos);
}

void testZh()
{
  char* str = "我也想过过过儿过过的生活";
  // 打印 str 的每个字符的内容编码
  for (int i = 0; str[i]; i++)
  {
    printf("str[%d] = %d\n", i, str[i]);
  }
}

int testStringNext(String str)
{
    print(str);
    return 0;
}


int main()
{
    // 测试 BF
    testBF();
    // 测试 KMP
    testKMP();
    testZh();
    testStringNext((String){"aaab", 4});
    testStringNext((String){"abcabcabc", 9});
    testStringNext((String){"ababcabc", 8});
    testStringNext((String){"ababcabcd", 9});
    testStringNext((String){"ABCDABCE", 8});
    testStringNext((String){"adsdad", 6});
    system("pause");
    return 0;
}